Madeleine được sinh ra tại Saint-Germain-en-Laye ở Pháp, là người con thứ 5 và là con gái thứ 3 của Vua François I của Pháp. Mẹ bà là Vương hậu Claude, con gái lớn của Vua Louis XII của Pháp và Anne của Bretagne, do đó Claude vừa là Vương hậu lại vừa mang tước hiệu Nữ Công tước của Brittany kế thừa từ mẹ.

Từ khi sinh ra Madeleine vốn đã yếu đuối, bà lớn lên ở vùng thung lũng sông Lit ấm áp và ôn hòa của Pháp thay vì ở Paris, vì Quốc vương Francis sợ rằng cái lạnh sẽ phá hủy sức khỏe mỏng manh của bà. Cùng với em gái Margaret, bà may mắn được người bác ruột của mình, Vương hậu Marguerite de Navarre, là chị gái bố ruột nuôi dưỡng và tiến hành giáo dục. Điều này kéo dài cho đến khi cha bà tái hôn và người vợ mới, Eleanor của Áo, thì họ mới đón bà về nhà riêng[1]. Lớn lên khó khăn như vậy, trước khi sinh nhật thứ 16 tuổi, công chúa Madeleine bắt đầu có biểu hiện bị mắc bệnh lao, một loại bệnh nan y vào thời điểm ấy.

Ba năm trước khi Madeleine ra đời, Hiệp ước Rouen của Pháp được thành lập để củng cố Liên minh Auld sau thất bại của Scotland tại Trận Flodden. Một cuộc hôn nhân với một Công chúa Pháp cho Quốc vương Scotland là James V, đây là một trong những điều khoản của hiệp ước này. Vì vậy vào tháng 4 năm 1530, John Stewart, Công tước xứ Albany, được bổ nhiệm làm ủy viên để hoàn tất cuộc hôn nhân giữa James V và Công chúa Madeleine[2].

Tuy nhiên, vì Madeleine không có sức khỏe tốt, một cô dâu người Pháp khác, Mary nhà Bourbon đã được đề xuất. Mary nhà Bourbon sẽ được tặng của hồi môn như thể cô là con gái của Quốc vương Pháp.